package leetbook.interview;

public class GasStation {

    public static void main(String[] args) {
        int[] gas = {1,2,3,4,5};
        int[] cost = {3,4,5,1,2};
        System.out.println(canCompleteCircuit(gas,cost));
    }

    public static int canCompleteCircuit1(int[] gas, int[] cost) {
        int n = gas.length;
        for(int i=0;i<n;i++){
            //从i开始环游，如果出现剩余油量<0，说明此路不通
            int count = 0; //走的路段数
            int leftGas = 0; //剩余油量
            while (count<n){
                //当前所在站点
                int cur = (i+count)%n;
                //把当前站点油都加上，走向下一个站点
                leftGas += gas[cur]-cost[cur];
                //查看此段路是否走成功了
                if(leftGas<0) break;
                count++;
            }
            if(count==n) return i;
        }
        return -1;
    }

    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        //如果从i开始后到j，但在前往j时出现油量不足，说明i...j-1都不能作为起始点
        //因为对于i<k<j，从i能到达k说明“到达k以后未加k的油之前，剩余油量不会为负”,而从k出发意味着“剩余油量只能为0”,这就更不可能到达j了
        //所以下一次起始直接从j开始即可
        for(int i=0;i<n;){
            //从i开始环游，如果出现剩余油量<0，说明此路不通
            int count = 0; //走的路段数
            int leftGas = 0; //剩余油量
            while (count<n){
                //当前所在站点
                int cur = (i+count)%n;
                //把当前站点油都加上，走向下一个站点
                leftGas += gas[cur]-cost[cur];
                //查看此段路是否走成功了
                if(leftGas<0) break;
                count++;
            }
            if(count==n) return i;
            //没走通，从停止的地方起始，如果停止的地方是之前排除过的，说明没有符合条件的起始点
            i = i+count+1;
        }
        return -1;
    }
}
